/*
 * 1235. 分解质因数
 * 将一个整数分解为若干质因数之乘积
 * https://www.lintcode.com/problem/prime-factorization/description
 * 
 * 样例
 * 给出 10, 返回 [2, 5].
 * 给出 660, 返回 [2, 2, 3, 5, 11].
 * 
 * 2018.06.09 @jeyming
 */
package prime_factorization_1235;

import java.util.ArrayList;
import java.util.List;

public class Prime_factorization_1235 {

    /**
     * @param num: An integer
     * @return: an integer array
     */
    public static List<Integer> primeFactorization(int num) {
        // write your code here
    	List<Integer> list = new ArrayList<>();
//    	boolean flag = false;
//    	int cnt = 1;
//    	int[] primeNum = new int[1000000057];
//    	primeNum[0] = 2;
//    	for(int i = 3; i<=1000000007; i+=2) {
//    		for(int j = 0; ; ++j) {
//    			if((i%primeNum[j]) != 0)
//    				break;
//    			flag=((primeNum[j]*primeNum[j]) <= i);
//    		}
//    		if(!flag) {
//    			primeNum[cnt] = i;
//    			while(num%primeNum[cnt-1] == 0) {
//    				list.add(primeNum[cnt-1]);
//    				num /= primeNum[cnt-1];
//    			}
//    			if(num == 0)
//    				break;
//    			++cnt;
//    		}
//    	}
    	for(Integer i = 2; i <= num; ++i) {
    		while(num % i == 0) {
    			list.add(i);
    			num /= i;
    		}
    	}
    	for(int i = 0; i < list.size(); ++i) {
    		System.out.println(list.get(i));
    	}
    	return list;
    }
    
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		primeFactorization(1000000007);
	}

}
